package com.itheima.leetcode.od.b.logicalsimulation;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

/**
 * <h3>池化资源共享</h3>
 * 有一个局部互联区域内的n台设备，每台设备都有一定数量的空闲资源，这些资源可以池化共享。用户会发起两种操作
 * <p>
 * 1.申请资源:输入 1 x，表示本次申请需要x个资源。系统要返回当前资源池中能满足此申请且剩余资源最少的设备ID;如果有多台设备满足条件，返回设备 ID 最小的;如果没有任何设备能满足，返回 0 并不做任何分配。
 * <p>
 * 2.释放资源:输入 2 y，表示将第y次申请(不一定是成功分配的那一次)释放回原设备。释放时，资源立即归还,
 * 且空闲资源自动连续，无需考虑空洞，
 * 给定n(1≤n≤ 1000)、操作次数 m(1≤m≤10^5)，以及初始时每台设备的空闲资源数 d[1]...d[n](1≤d≤1000)，以及接下来 m 行操作，输出每次“申请”操作的返回值。
 * <p>
 * 输入描述
 * <p>
 * 第一行，输入n和 m
 * <p>
 * 第二行输入n台设备的初始空闲资源数
 * <p>
 * 接下来m行，输出要执行的操作，
 * <p>
 * 输出描述
 * <p>
 * 输出每次“申请”操作的返回值。
 * <p>
 * 示例1：
 * <p>
 * 输入：
 * <p>
 * 2 2
 * <p>
 * 100 500
 * <p>
 * 1 40
 * <p>
 * 1 450
 * <p>
 * <p>
 * 输出：
 * <p>
 * 1 2
 */
public class PoolingResourceSharing {
    public static void main(String[] args) {
        int[][] array = Arrays.stream("1 40\n1 450".split("\n"))
                .map(s -> Arrays.stream(s.split(" "))
                        .mapToInt(Integer::parseInt)
                        .toArray())
                .toArray(int[][]::new);
        // 每台设备的当前空闲资源数
        int[] deviceResources = Arrays.stream("100 500".split(" "))
                .mapToInt(Integer::parseInt)
                .toArray();

        System.out.println(solve(deviceResources, array));
    }

    /**
     * 资源池化系统模拟
     *
     * @param deviceResources
     * @param array
     * @return
     */
    public static String solve(int[] deviceResources, int[][] array) {

        int n = 2;  // 设备数量
        int m = 2;  // 操作数量

        // 存储每次申请操作的结果
        List<AllocationRecord> allocationRecords = new ArrayList<>();

        // 存储申请操作的返回值
        List<Integer> results = new ArrayList<>();

        // 处理m个操作
        for (int op = 0; op < m; op++) {
            int operationType = array[op][0];

            if (operationType == 1) {  // 申请资源操作
                int x = array[op][1];  // 申请的资源数量

                // 找到能满足申请且剩余资源最少的设备
                int bestDevice = -1;  // -1表示未找到合适设备
                int minRemaining = Integer.MAX_VALUE;

                // 遍历所有设备
                for (int i = 0; i < n; i++) {
                    int currentResources = deviceResources[i];

                    // 检查设备是否能满足申请
                    if (currentResources >= x) {
                        int remaining = currentResources - x;

                        // 更新最佳设备：剩余资源更少，或剩余相同但设备ID更小
                        if (remaining < minRemaining || (remaining == minRemaining && i < bestDevice)) {
                            bestDevice = i;
                            minRemaining = remaining;
                        }
                    }
                }

                if (bestDevice != -1) {
                    // 申请成功
                    int deviceId = bestDevice + 1;  // 转回1-based
                    deviceResources[bestDevice] -= x;  // 分配资源
                    allocationRecords.add(new AllocationRecord(deviceId, x));
                    results.add(deviceId);
                } else {
                    // 申请失败
                    allocationRecords.add(new AllocationRecord(0, x));  // 记录失败的申请
                    results.add(0);
                }

            } else if (operationType == 2) {  // 释放资源操作
                int y = array[op][1];  // 第y次申请的序号（1-based）

                // 检查申请序号是否有效
                if (y >= 1 && y <= allocationRecords.size()) {
                    AllocationRecord record = allocationRecords.get(y - 1);  // 转为0-based

                    // 只有成功分配的申请才需要释放资源
                    if (record.deviceId > 0) {
                        deviceResources[record.deviceId - 1] += record.resourceAmount;  // 归还资源
                    }
                }
            }
        }

        // 输出结果
        return results.stream()
                .map(String::valueOf)
                .collect(Collectors.joining(" "));
    }

    /**
     * 申请记录类
     */
    static class AllocationRecord {
        int deviceId;      // 分配的设备ID（0表示申请失败）

        int resourceAmount; // 申请的资源数量

        public AllocationRecord(int deviceId, int resourceAmount) {
            this.deviceId = deviceId;
            this.resourceAmount = resourceAmount;
        }
    }
}